今天就是瘋狂在這題上吃 Wrong Answer 與 TLE，因此以下就是紀錄我刷題時的錯誤想法們。

1353. Maximum Number of Events That Can Be Attended

題目: 給定一個活動陣列，其中 events[i] = [startDayi, endDayi]。我的每個活動都在 startDayi 開始並在 endDayi 結束。而我能活動開始至結束的任一天，參加這活動，而一天只能參加一個活動。返回返回我全部可以參加的最多活動數量。

(這題好像是 Greedy 的經典題。)

錯誤的第一個想法
先排序活動區間短的，後排開始時間早的。
並接著這排序的活動的活動開始日逐一取起。

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        if ((a[1] - a[0]) != (b[1] - b[0])) {
            return (a[1] - a[0]) < (b[1] - b[0])
        }
        return a[0] < b[0]; 
    }
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end(), cmp);
        // ...
	}
};

反例:

[[1,1], [2,2], [3,4], [1,3]]

這解: 第四個活動時 [1,2,3] 日時都被佔了，導致最多只取到了3個。第四天沒參加活動。

錯誤的第二個想法:
先排結束時間早的，後排開始時間早的。
按此順序看哪個活動可以，並排除比此活動開始日更早的時間。

	static bool cmp(vector<int>& a, vector<int>& b) {
		if (a[1] != b[1]) {
			return a[1] < b[1]; // Sort by end day first
		}
		return a[0] < a[0];
	}
  int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end(), cmp);
        int res = 0;
        int j = 0;
        for (int i = 0; i < 1e5; i++) {
            if (events[j][0] <= i && events[j++][1] >= i)
                res++;
            if (j >= events.size())
                break;
        }
        return res;
    }
};

反例

[[1,5],[1,5],[1,5],[2,3],[2,3]]
排序過後: [2, 3] [2, 3] [1, 5] [1, 5] [1, 5]

for 迴圈裡的 i 是代表日期指針，考慮完前兩個活動後，日期指針已經跑到 3 之後，因此活動陣列裡後三個 [1, 5] 只能選在第4, 5 天參加。(第一天就沒參加到活動)

第三想法:
先排結束時間，後排開始時間。把每個 event 從開始日到最後都選選看。

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[1] != b[1]) {
            return a[1] < b[1];  // Sort by end day first
        }
        return a[0] < b[0];  // Then by start day
    }

    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end(), cmp);
        
        int res = 0;
        int i = 0;
        int n = events.size();
        vector<bool> attended(100001, false);
        
        for (const auto& event : events) {
            for (int day = event[0]; day <= event[1]; day++) {
                if (!attended[day]) {
                    attended[day] = true;
                    res++;
                    break;
                }
            }
        }
        
        return res;
    }
};

吃 TLE，複雜度達: $n^2$ 。
反例:
活動有 1e5 個，每個活動有 1e5 天，以上跑達 100000000 次 = 1 億次。

最後看這位的解題:
【每日一题】1353. Maximum Number of Events That Can Be Attended,

sort 起始時間，並用 minheap 存結束時間。

1. 先根據活動的開始日進行排序。
2. 對於每一天，我們將當天或之前開始的活動加入 min-heap，並儘可能參加一個結束日最早的活動。
3. 當天參加完活動後，將該活動從 heap 中移除。
4. 重複此過程，直到所有活動都被處理完畢或所有天數結束。

概念:

挑能做任務中最緊急死線的先做啊!

想想這跟我趕作業時，應該要做的排序策略一樣啊!